package com.ls.day16;

/**
 * @author ：xxx
 * @description：TODO
 * @date ：2021/4/1 10:09
 */
public class Trap {

    public static void main(String[] args) {
        int[] height = new int[]{4,2,0,3,2,5};
        System.out.println(trap(height));
    }

    public static int trap(int[] height) {
        if (height.length==0)return 0;
        int sum=0,i=0;
        int[] left_height = new int[height.length];
        int[] right_height = new int[height.length];
        //左边的最大高度
        int h=height[0];
        for (i=1;i<height.length-1;i++){
            h = Math.max(h,height[i]);
            left_height[i]=h;
        }

        //右边的最大高度
        h=height[height.length-1];
        for (i=height.length-2;i>0;i--){
            h = Math.max(h,height[i]);
            right_height[i]=h;
        }

        for (i=1;i<height.length-1;i++){
            sum+=Math.min(left_height[i],right_height[i])-height[i];
        }
        return sum;
    }
}
